package java学习.算法.动态规划.暴力递归与动态规划;

import javax.servlet.jsp.PageContext;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/30 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 礼物的最大价值 {

    public static void main(String[] args) {
//        [[1,3,1],[1,5,1],[4,2,1]]
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(maxValue(grid));
        System.out.println(maxValue1(grid));
        System.out.println(maxValue2(grid));
        System.out.println(maxValue3(grid));


    }

/*
    在一个 m × n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
    你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
    给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
     如输入这样的一个二维数组，
        [
        [1,3,1],
        [1,5,1],
        [4,2,1]
        ]
    那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12
     */
//    暴力
    public   static int maxValue (int[][] grid) {
        // write code here
        return  process(grid,0,0);
    }

    public static int process(int[][] grid, int i, int j) {
    int sum = 0 , process=0,process1=0;
     int hang = grid.length;
     int lie=  grid[0].length;;
//        for (int k = 0; k < hang; k++) {
//           lie =  grid[k].length;
//        }
      if (i==hang-1 &&j==lie-1){
          return grid[i][j];
      }
      if (i==hang-1){
          return grid[i][j] +process(grid,i,j+1);
      }
        if (j==lie-1){
            return grid[i][j] +process(grid,i+1,j);
        }
        process = process(grid, i + 1, j);

        process1 = process(grid, i, j + 1);

        return Math.max(process,process1)+grid[i][j];
    }

//    找规律
    public   static int maxValue1 (int[][] grid) {
        int hang = grid.length;
        int lie=  grid[0].length;
        for (int i = 1; i < hang; i++) {
            grid[i][0] = grid[i][0]+ grid[i-1][0];
        }
        for (int j = 1; j < lie; j++) {
            grid[0][j] = grid[0][j]+ grid[0][j-1];
        }
        for (int i = 1; i < hang; i++) {
            for (int j = 1; j < lie; j++) {

                grid[i][j]=Math.max(grid[i-1][j],grid[i][j-1])+grid[i][j];
            }
        }
        return  grid[hang-1][lie-1];

    }

    //    找规律
    public   static int maxValue2 (int[][] grid) {
        int hang = grid.length;
        int lie=  grid[0].length;
        int [][] dp = new int[hang][lie];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < hang; i++) {
            for (int j = 0; j < lie; j++) {
                if (i==0&&j==0){
                   continue;
                }
                if (i==0){
                    dp[i][j] = grid[i][j]+ dp[i][j-1];
                }
                else if (j==0){
                    dp[i][j] = grid[i][j]+ dp[i-1][j];
                }
                else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
                }
            }
        }
        return  dp[hang-1][lie-1];

    }
    public static int maxValue3(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=grid[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0&&j==0) continue;
                if (i==0) {
                    dp[i][j]=dp[i][j-1]+grid[i][j];//如果去上边界，此时只有可能是向右走
                }else if (j==0) {
                    dp[i][j]=dp[i-1][j]+grid[i][j];//如果去左边界，此时只有可能是向下走
                }else{
                    dp[i][j]=grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);//如果不是边界，那么就取向下走和向右走的最佳收益
                }
            }
        }
        return dp[m-1][n-1];
    }

}
